package com.lw.leetcode.linked.b;

import com.lw.leetcode.linked.Node;

/**
 * Created with IntelliJ IDEA.
 * 430. 扁平化多级双向链表
 * 剑指 Offer II 028. 展平多级双向链表
 *
 * @author liw
 * @version 1.0
 * @date 2021/8/26 15:55
 */
public class Flatten {

    public static void main(String[] args) {
        Flatten test = new Flatten();
        Node instance = Node.getInstance();
        Node flatten = test.flatten(instance);
        System.out.println(flatten);
    }

    public Node flatten(Node head) {
        find(head);
        return head;
    }

    private Node find(Node node) {
        Node last = null;
        while (node != null) {
            if (node.child == null) {
                last = node;
                node = node.next;
                continue;
            }
            Node st = node.child;

            Node end = find(st);

            end.next = node.next;
            if (node.next != null) {
                node.next.prev = end;
            }
            node.next = st;
            node.child = null;
            st.prev = node;
            node = end.next;
            last = end;
        }
        return last;
    }

}
